package hot100;

import pojo.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * https://leetcode.cn/problems/symmetric-tree/
 */
public class IsSymmetric101 {

    //队列
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root.left);
        deque.addLast(root.right);
        while (!deque.isEmpty()){
            TreeNode A = deque.poll();
            TreeNode B = deque.poll();
            if (A==null && B==null){
                continue;
            }
            if (A!=null && B!=null){
                if (A.val == B.val){
                    deque.addLast(A.left);
                    deque.addLast(B.right);
                    deque.addLast(A.right);
                    deque.addLast(B.left);
                    continue;
                }
            }
            return false;
        }
        return true;
    }

    //递归
    public boolean isSymmetric2(TreeNode root) {
        if(root==null) {
            return true;
        }
        //调用递归函数，比较左节点，右节点
        return dfs(root.left,root.right);
    }

    boolean dfs(TreeNode left, TreeNode right) {
        //递归的终止条件是两个节点都为空
        //或者两个节点中有一个为空
        //或者两个节点的值不相等
        if(left==null && right==null) {
            return true;
        }
        if(left==null || right==null) {
            return false;
        }
        if(left.val!=right.val) {
            return false;
        }
        //再递归的比较 左节点的左孩子 和 右节点的右孩子
        //以及比较  左节点的右孩子 和 右节点的左孩子
        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }


}
